#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#include <string.h>
#include "maze.h"

Maze*	Maze_create(int width, int height) {
	//make sure width and height are odd because it makes more beautiful maze
	width += (width + 1) % 2;
	height += (height + 1) % 2;

	//initialize maze
	Maze* m = (Maze*)malloc(sizeof(Maze));
	(*m).height = height;
	(*m).width = width;
	(*m).map = (char*)malloc(width * height * sizeof(char));
	int i, j;
	for(i = 0; i < width; ++i) {
		for(j = 0; j < height; ++j) {
			(*m).map[j * width + i] = i % 2 == 0 && j % 2 == 0 ? TILE_WALKABLE : TILE_WALL;
		}
	}

	//return created maze
	return m;
}

void Maze_destroy(Maze* m) {
	free((*m).map);
	free(m);
}

void Maze_randomize(Maze* m) {
	//temps
	int width	= (*m).width;
	int height	= (*m).height;

	//init maze
	int i, j;
	for(i = 0; i < width; ++i) {
		for(j = 0; j < height; ++j) {
			(*m).map[j * width + i] = i % 2 == 0 && j % 2 == 0 ? TILE_WALKABLE : TILE_WALL;
		}
	}

	////build temp storages
	//visited cells
	int hw = (width >> 1) + (width % 2);
	int hh = (height >> 1) + (height % 2);
	char* visited = (char*)malloc(hw*hh*sizeof(char));
	for(i = 0; i < hw*hh; ++i) visited[i] = 0;

	//travelled directions stack
	char dir[4] = { 0, 1, 2, 3 };
	char* travelledDirs = (char*)malloc(hw*hh*sizeof(char));
	int stackIdx = 0;

	////start making random maze
	//initialize to random pos
	srand(time(0));
	int x = rand() % hw;
	int y = rand() % hh;
	visited[y*hw+x] = 1;

	//until all cell is travelled
	for(i = 0; i < hw*hh - 1; ++i) {
		//generate rand dir
		for(int j = 0; j < 4; ++j) {
			int i1 = rand()%4;
			int i2 = rand()%4;
			char temp = dir[i1];
			dir[i1] = dir[i2];
			dir[i2] = temp;
		}

		//go to new random position
		int found = 0;
		while(!found) {
			int nextX, nextY;
			char selectedDir = 0;
			for(int j = 0; j < 4; ++j) {
				nextX = x;
				nextY = y;
				selectedDir = dir[j];
				switch(selectedDir) {
					case 0 :
						//go right
						nextX += 1;
						break;
					case 1 :
						//go left
						nextX -= 1;
						break;
					case 2 :
						//go down
						nextY += 1;
						break;
					case 3 :
						//go up
						nextY -= 1;
						break;
				}

				found = (Maze_isInBounds(m, nextX << 1, nextY << 1) && !visited[nextY * hw + nextX]);
				if(found) break;
			}

			//if new cell found
			if(found) {
				//push dir to stack
				travelledDirs[stackIdx++] = selectedDir;

				//make a new way
				int xx = x*2 + (nextX - x);
				int yy = y*2 + (nextY - y);
				(*m).map[yy * width + xx] = TILE_WALKABLE;
				
				//mark as visited
				x = nextX;
				y = nextY;
				visited[y * hw + x] = 1;

				//draw
				//Maze_draw(m, 0, 0, 0, 0);
			}

			//no cell found, backtrack!
			else {
				selectedDir = travelledDirs[--stackIdx];
				switch(selectedDir) {
					case 0 :
						//go right
						x += -1;
						break;
					case 1 :
						//go left
						x -= -1;
						break;
					case 2 :
						//go down
						y += -1;
						break;
					case 3 :
						//go up
						y -= -1;
						break;
				}
			}
		}
	}

	////free allocated temporaries
	free(travelledDirs);
	free(visited);
}

int Maze_isWalkable(Maze* m, int x, int y) {
	return Maze_isInBounds(m, x, y) && (*m).map[y*(*m).width+x] == TILE_WALKABLE;
}

int	Maze_isInBounds(Maze* m, int x, int y) {
	return x >= 0 && x < (*m).width && y >= 0 && y < (*m).height;
}
